Visual Cafe 3/Visual Cafe 3.ISO/Vcafe/JFC.bin/DefaultMutableTreeNode.java

Text File | 1998-06-30 | 44KB | 1,492 lines

/*
 * @(#)DefaultMutableTreeNode.java    1.7 98/04/02
 *
 * Copyright (c) 1997 Sun Microsystems, Inc. All Rights Reserved.
 *
 * This software is the confidential and proprietary information of Sun
 * Microsystems, Inc. ("Confidential Information").  You shall not
 * disclose such Confidential Information and shall use it only in
 * accordance with the terms of the license agreement you entered into
 * with Sun.
 *
 * SUN MAKES NO REPRESENTATIONS OR WARRANTIES ABOUT THE SUITABILITY OF THE
 * SOFTWARE, EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR
 * PURPOSE, OR NON-INFRINGEMENT. SUN SHALL NOT BE LIABLE FOR ANY DAMAGES
 * SUFFERED BY LICENSEE AS A RESULT OF USING, MODIFYING OR DISTRIBUTING
 * THIS SOFTWARE OR ITS DERIVATIVES.
 *
 */

package com.sun.java.swing.tree;
   // ISSUE: this class depends on nothing in AWT -- move to java.util?

import java.io.*;
import java.util.*;


/**
 * A <code>DefaultMutableTreeNode</code> is a general-purpose node in a tree data
 * structure. A tree node may have at most one parent and 0 or more children.
 * <code>DefaultMutableTreeNode</code> provides operations for examining and modifying a
 * node's parent and children and also operations for examining the tree that
 * the node is a part of.  A node's tree is the set of all nodes that can be
 * reached by starting at the node and following all the possible links to
 * parents and children.  A node with no parent is the root of its tree; a
 * node with no children is a leaf.  A tree may consist of many subtrees,
 * each node acting as the root for its own subtree.
 * <p>
 * This class provides enumerations for efficiently traversing a tree or
 * subtree in various orders or for following the path between two nodes.
 * A <code>DefaultMutableTreeNode</code> may also hold a reference to a user object, the
 * use of which is left to the user.  Asking a <code>DefaultMutableTreeNode</code> for its
 * string representation with <code>toString()</code> returns the string
 * representation of its user object.
 * <p>
 * <b>This is not a thread safe class.</b>If you intend to use
 * a DefaultMutableTreeNode (or a tree of TreeNodes) in more than one thread, you
 * need to do your own synchronizing. A good convention to adopt is
 * synchronizing on the root node of a tree.
 * <p>
 * While DefaultMutableTreeNode implements the MutableTreeNode interface and
 * will allow you to add in any implementation of MutableTreeNode not all
 * of the methods in DefaultMutableTreeNode will be applicable to all
 * MutableTreeNodes implementations. Especially with some of the enumerations
 * that are provided, using some of these methods assumes the
 * DefaultMutableTreeNode contains only DefaultMutableNode instances. All
 * of the TreeNode/MutableTreeNode methods will behave as defined no
 * matter what implementations are added.
 * <p>
 * Warning: serialized objects of this class will not be compatible with
 * future swing releases.  The current serialization support is appropriate
 * for short term storage or RMI between Swing1.0 applications.  It will
 * not be possible to load serialized Swing1.0 objects with future releases
 * of Swing.  The JDK1.2 release of Swing will be the compatibility
 * baseline for the serialized form of Swing objects.
 *
 * @see MutableTreeNode
 *
 * @version 1.7 04/02/98
 * @author Rob Davis
 */
public class DefaultMutableTreeNode extends Object implements Cloneable,
       MutableTreeNode, Serializable
{

    /**
     * A null-enumeration class returned when an enumeration of a
     * leaf node's children is requested.
     */
    static public final Enumeration EMPTY_ENUMERATION
    = new Enumeration() {
        public boolean hasMoreElements() { return false; }
        public Object nextElement() {
        throw new NoSuchElementException("No more elements");
        }
    };

    /** this node's parent, or null if this node has no parent */
    protected MutableTreeNode   parent;

    /** array of children, may be null if this node has no children */
    protected Vector        children;

    /** optional user object */
    transient protected Object    userObject;

    /** true if the node is able to have children */
    protected boolean        allowsChildren;


    /**
     * Creates a tree node that has no parent and no children, but which
     * allows children.
     */
    public DefaultMutableTreeNode() {
    this(null);
    }

    /**
     * Creates a tree node with no parent, no children, but which allows
     * children, and initializes it with the specified user object.
     *
     * @param userObject an Object provided by the user that constitutes
     *                   the node's data
     */
    public DefaultMutableTreeNode(Object userObject) {
    this(userObject, true);
    }

    /**
     * Creates a tree node with no parent, no children, initialized with
     * the specified user object, and that allows children only if
     * specified.
     *
     * @param userObject an Object provided by the user that constitutes
     *        the node's data
     * @param allowsChildren if true, the node is allowed to have child
     *        nodes -- otherwise, it is always a leaf node
     */
    public DefaultMutableTreeNode(Object userObject, boolean allowsChildren) {
    super();
    parent = null;
    this.allowsChildren = allowsChildren;
    this.userObject = userObject;
    }


    //
    //  Primitives
    //

    /**
     * Removes <code>newChild</code> from its present parent (if it has a
     * parent), sets the child's parent to this node, and then adds the child
     * to this node's child array at index <code>childIndex</code>.
     * <code>newChild</code> must not be null and must not be an ancestor of
     * this node.
     *
     * @param    newChild    the MutableTreeNode to insert under this node
     * @param    childIndex    the index in this node's child array
     *                where this node is to be inserted
     * @exception    ArrayIndexOutOfBoundsException    if
     *                <code>childIndex</code> is out of bounds
     * @exception    IllegalArgumentException    if
     *                <code>newChild</code> is null or is an
     *                ancestor of this node
     * @exception    IllegalStateException    if this node does not allow
     *                        children
     * @see    #isNodeDescendant
     */
    public void insert(MutableTreeNode newChild, int childIndex) {
    if (!allowsChildren) {
        throw new IllegalStateException("node does not allow children");
    } else if (newChild == null) {
        throw new IllegalArgumentException("new child is null");
    } else if (isNodeAncestor(newChild)) {
        throw new IllegalArgumentException("new child is an ancestor");
    }

        MutableTreeNode oldParent = (MutableTreeNode)newChild.getParent();

        if (oldParent != null) {
        oldParent.remove(newChild);
        }
        newChild.setParent(this);
        if (children == null) {
        children = new Vector();
        }
        children.insertElementAt(newChild, childIndex);
    }

    /**
     * Removes the child at the specified index from this node's children
     * and sets that node's parent to null. The child node to remove
     * must be a <code>MutableTreeNode</code>.
     *
     * @param    childIndex    the index in this node's child array
     *                of the child to remove
     * @exception    ArrayIndexOutOfBoundsException    if
     *                <code>childIndex</code> is out of bounds
     */
    public void remove(int childIndex) {
    MutableTreeNode child = (MutableTreeNode)getChildAt(childIndex);
    children.removeElementAt(childIndex);
    child.setParent(null);
    }

    /**
     * Sets this node's parent to <code>newParent</code> but does not
     * change the parent's child array.  This method is called from
     * <code>insert()</code> and <code>remove()</code> to
     * reassign a child's parent, it should not be messaged from anywhere
     * else.
     *
     * @param    newParent    this node's new parent
     */
    public void setParent(MutableTreeNode newParent) {
    parent = newParent;
    }

    /**
     * Returns this node's parent or null if this node has no parent.
     *
     * @return    this node's parent TreeNode, or null if this node has no parent
     */
    public TreeNode getParent() {
    return parent;
    }

    /**
     * Returns the child at the specified index in this node's child array.
     *
     * @param    index    an index into this node's child array
     * @exception    ArrayIndexOutOfBoundsException    if <code>index</code>
     *                        is out of bounds
     * @return    the TreeNode in this node's child array at  the specified index
     */
    public TreeNode getChildAt(int index) {
    if (children == null) {
        throw new ArrayIndexOutOfBoundsException("node has no children");
    }
    return (TreeNode)children.elementAt(index);
    }

    /**
     * Returns the number of children of this node.
     *
     * @return    an int giving the number of children of this node
     */
    public int getChildCount() {
    if (children == null) {
        return 0;
    } else {
        return children.size();
    }
    }

    /**
     * Returns the index of the specified child in this node's child array.
     * If the specified node is not a child of this node, returns
     * <code>-1</code>.  This method performs a linear search and is O(n)
     * where n is the number of children.
     *
     * @param    aChild    the TreeNode to search for among this node's children
     * @exception    IllegalArgumentException    if <code>aChild</code>
     *                            is null
     * @return    an int giving the index of the node in this node's child
     *          array, or <code>-1</code> if the specified node is a not
     *          a child of this node
     */
    public int getIndex(TreeNode aChild) {
    if (aChild == null) {
        throw new IllegalArgumentException("argument is null");
    }

    if (!isNodeChild(aChild)) {
        return -1;
    }
    return children.indexOf(aChild);    // linear search
    }

    /**
     * Creates and returns a forward-order enumeration of this node's
     * children.  Modifying this node's child array invalidates any child
     * enumerations created before the modification.
     *
     * @return    an Enumeration of this node's children
     */
    public Enumeration children() {
    if (children == null) {
        return EMPTY_ENUMERATION;
    } else {
        return children.elements();
    }
    }

    /**
     * Determines whether or not this node is allowed to have children.
     * If <code>allows</code> is false, all of this node's children are
     * removed.
     * <p>
     * Note: By default, a node allows children.
     *
     * @param    allows    true if this node is allowed to have children
     */
    public void setAllowsChildren(boolean allows) {
    if (allows != allowsChildren) {
        allowsChildren = allows;
        if (!allowsChildren) {
        removeAllChildren();
        }
    }
    }

    /**
     * Returns true if this node is allowed to have children.
     *
     * @return    true if this node allows children, else false
     */
    public boolean getAllowsChildren() {
    return allowsChildren;
    }

    /**
     * Sets the user object for this node to <code>userObject</code>.
     *
     * @param    userObject    the Object that constitutes this node's
     *                          user-specified data
     * @see    #getUserObject
     * @see    #toString
     */
    public void setUserObject(Object userObject) {
    this.userObject = userObject;
    }

    /**
     * Returns this node's user object.
     *
     * @return    the Object stored at this node by the user
     * @see    #setUserObject
     * @see    #toString
     */
    public Object getUserObject() {
    return userObject;
    }


    //
    //  Derived methods
    //

    /**
     * Removes the subtree rooted at this node from the tree, giving this
     * node a null parent.  Does nothing if this node is the root of its
     * tree.
     */
    public void removeFromParent() {
    MutableTreeNode parent = (MutableTreeNode)getParent();
    if (parent != null) {
        parent.remove(this);
    }
    }

    /**
     * Removes <code>aChild</code> from this node's child array, giving it a
     * null parent.
     *
     * @param    aChild    a child of this node to remove
     * @exception    IllegalArgumentException    if <code>aChild</code>
     *                    is null or is not a child of this node
     */
    public void remove(MutableTreeNode aChild) {
    if (aChild == null) {
        throw new IllegalArgumentException("argument is null");
    }

    if (!isNodeChild(aChild)) {
        throw new IllegalArgumentException("argument is not a child");
    }
    remove(getIndex(aChild));    // linear search
    }

    /**
     * Removes all of this node's children, setting their parents to null.
     * If this node has no children, this method does nothing.
     */
    public void removeAllChildren() {
    for (int i = getChildCount()-1; i >= 0; i--) {
        remove(i);
    }
    }

    /**
     * Removes <code>newChild</code> from its parent and makes it a child of
     * this node by adding it to the end of this node's child array.
     *
     * @see        #insert
     * @param    newChild    node to add as a child of this node
     * @exception    IllegalArgumentException    if <code>newChild</code>
     *                        is null
     * @exception    IllegalStateException    if this node does not allow
     *                        children
     */
    public void add(MutableTreeNode newChild) {
    if(newChild != null && newChild.getParent() == this)
        insert(newChild, getChildCount() - 1);
    else
        insert(newChild, getChildCount());
    }



    //
    //  Tree Queries
    //

    /**
     * Returns true if <code>anotherNode</code> is an ancestor of this node
     * -- if it is this node, this node's parent, or an ancestor of this
     * node's parent.  (Note that a node is considered an ancestor of itself.)
     * If <code>anotherNode</code> is null, this method returns false.  This
     * operation is at worst O(h) where h is the distance from the root to
     * this node.
     *
     * @see        #isNodeDescendant
     * @see        #getSharedAncestor
     * @param    anotherNode    node to test as an ancestor of this node
     * @return    true if this node is a descendant of <code>anotherNode</code>
     */
    public boolean isNodeAncestor(TreeNode anotherNode) {
    if (anotherNode == null) {
        return false;
    }

    TreeNode ancestor = this;

    do {
        if (ancestor == anotherNode) {
        return true;
        }
    } while((ancestor = ancestor.getParent()) != null);

    return false;
    }

    /**
     * Returns true if <code>anotherNode</code> is a descendant of this node
     * -- if it is this node, one of this node's children, or a descendant of
     * one of this node's children.  Note that a node is considered a
     * descendant of itself.  If <code>anotherNode</code> is null, returns
     * false.  This operation is at worst O(h) where h is the distance from the
     * root to <code>anotherNode</code>.
     *
     * @see    #isNodeAncestor
     * @see    #getSharedAncestor
     * @param    anotherNode    node to test as descendant of this node
     * @return    true if this node is an ancestor of <code>anotherNode</code>
     */
    public boolean isNodeDescendant(DefaultMutableTreeNode anotherNode) {
    if (anotherNode == null)
        return false;

    return anotherNode.isNodeAncestor(this);
    }

    /**
     * Returns the nearest common ancestor to this node and <code>aNode</code>.
     * Returns null, if no such ancestor exists -- if this node and
     * <code>aNode</code> are in different trees or if <code>aNode</code> is
     * null.  A node is considered an ancestor of itself.
     *
     * @see    #isNodeAncestor
     * @see    #isNodeDescendant
     * @param    aNode    node to find common ancestor with
     * @return    nearest ancestor common to this node and <code>aNode</code>,
     *        or null if none
     */
    public TreeNode getSharedAncestor(DefaultMutableTreeNode aNode) {
    if (aNode == this) {
        return this;
    } else if (aNode == null) {
        return null;
    }

    int        level1, level2, diff;
    TreeNode    node1, node2;

    level1 = getLevel();
    level2 = aNode.getLevel();

    if (level2 > level1) {
        diff = level2 - level1;
        node1 = aNode;
        node2 = this;
    } else {
        diff = level1 - level2;
        node1 = this;
        node2 = aNode;
    }

    // Go up the tree until the nodes are at the same level
    while (diff > 0) {
        node1 = node1.getParent();
        diff--;
    }

    // Move up the tree until we find a common ancestor.  Since we know
    // that both nodes are at the same level, we won't cross paths
    // unknowingly (if there is a common ancestor, both nodes hit it in
    // the same iteration).

    do {
        if (node1 == node2) {
        return node1;
        }
        node1 = node1.getParent();
        node2 = node2.getParent();
    } while (node1 != null);// only need to check one -- they're at the
    // same level so if one is null, the other is

    if (node1 != null || node2 != null) {
        throw new InternalError ("nodes should be null");
    }

    return null;
    }


    /**
     * Returns true if and only if <code>aNode</code> is in the same tree
     * as this node.  Returns false if <code>aNode</code> is null.
     *
     * @see    #getSharedAncestor
     * @see    #getRoot
     * @return    true if <code>aNode</code> is in the same tree as this node;
     *        false if <code>aNode</code> is null
     */
    public boolean isNodeRelated(DefaultMutableTreeNode aNode) {
    return (aNode != null) && (getRoot() == aNode.getRoot());
    }


    /**
     * Returns the depth of the tree rooted at this node -- the longest
     * distance from this node to a leaf.  If this node has no children,
     * returns 0.  This operation is much more expensive than
     * <code>getLevel()</code> because it must effectively traverse the entire
     * tree rooted at this node.
     *
     * @see    #getLevel
     * @return    the depth of the tree whose root is this node
     */
    public int getDepth() {
    Object    last = null;
    Enumeration    enum = breadthFirstEnumeration();

    while (enum.hasMoreElements()) {
        last = enum.nextElement();
    }

    if (last == null) {
        throw new InternalError ("nodes should be null");
    }

    return ((DefaultMutableTreeNode)last).getLevel() - getLevel();
    }



    /**
     * Returns the number of levels above this node -- the distance from
     * the root to this node.  If this node is the root, returns 0.
     *
     * @see    #getDepth
     * @return    the number of levels above this node
     */
    public int getLevel() {
    TreeNode ancestor;
    int levels = 0;

    ancestor = this;
    while((ancestor = ancestor.getParent()) != null){
        levels++;
    }

    return levels;
    }


    /**
      * Returns the path from the root, to get to this node.  The last
      * element in the path is this node.
      *
      * @return an array of TreeNode objects giving the path, where the
      *         first element in the path is the root and the last
      *         element is this node.
      */
    public TreeNode[] getPath() {
    return getPathToRoot(this, 0);
    }

    /**
     * Builds the parents of node up to and including the root node,
     * where the original node is the last element in the returned array.
     * The length of the returned array gives the node's depth in the
     * tree.
     *
     * @param aNode  the TreeNode to get the path for
     * @param depth  an int giving the number of steps already taken towards
     *        the root (on recursive calls), used to size the returned array
     * @return an array of TreeNodes giving the path from the root to the
     *         specified node
     */
    protected TreeNode[] getPathToRoot(TreeNode aNode, int depth) {
    TreeNode[]              retNodes;

    /* Check for null, in case someone passed in a null node, or
       they passed in an element that isn't rooted at root. */
    if(aNode == null) {
        if(depth == 0)
        return null;
        else
        retNodes = new TreeNode[depth];
    }
    else {
        depth++;
        retNodes = getPathToRoot(aNode.getParent(), depth);
        retNodes[retNodes.length - depth] = aNode;
    }
    return retNodes;
    }

    /**
      * Returns the user object path, from the root, to get to this node.
      * If some of the TreeNodes in the path have null user objects, the
      * returned path will contain nulls.
      */
    public Object[] getUserObjectPath() {
    TreeNode[]          realPath = getPath();
    Object[]            retPath = new Object[realPath.length];

    for(int counter = 0; counter < realPath.length; counter++)
        retPath[counter] = ((DefaultMutableTreeNode)realPath[counter])
                       .getUserObject();
    return retPath;
    }

    /**
     * Returns the root of the tree that contains this node.  The root is
     * the ancestor with a null parent.
     *
     * @see    #isNodeAncestor
     * @return    the root of the tree that contains this node
     */
    public TreeNode getRoot() {
    TreeNode ancestor = this;
    TreeNode previous;

    do {
        previous = ancestor;
        ancestor = ancestor.getParent();
    } while (ancestor != null);

    return previous;
    }


    /**
     * Returns true if this node is the root of the tree.  The root is
     * the only node in the tree with a null parent; every tree has exactly
     * one root.
     *
     * @return    true if this node is the root of its tree
     */
    public boolean isRoot() {
    return getParent() == null;
    }


    /**
     * Returns the node that follows this node in a preorder traversal of this
     * node's tree.  Returns null if this node is the last node of the
     * traversal.  This is an inefficient way to traverse the entire tree; use
     * an enumeration, instead.
     *
     * @see    #preorderEnumeration
     * @return    the node that follows this node in a preorder traversal, or
     *        null if this node is last
     */
    public DefaultMutableTreeNode getNextNode() {
    if (getChildCount() == 0) {
        // No children, so look for nextSibling
        DefaultMutableTreeNode nextSibling = getNextSibling();

        if (nextSibling == null) {
        DefaultMutableTreeNode aNode = (DefaultMutableTreeNode)getParent();

        do {
            if (aNode == null) {
            return null;
            }

            nextSibling = aNode.getNextSibling();
            if (nextSibling != null) {
            return nextSibling;
            }

            aNode = (DefaultMutableTreeNode)aNode.getParent();
        } while(true);
        } else {
        return nextSibling;
        }
    } else {
        return (DefaultMutableTreeNode)getChildAt(0);
    }
    }


    /**
     * Returns the node that precedes this node in a preorder traversal of
     * this node's tree.  Returns null if this node is the first node of the
     * traveral -- the root of the tree.  This is an inefficient way to
     * traverse the entire tree; use an enumeration, instead.
     *
     * @see    #preorderEnumeration
     * @return    the node that precedes this node in a preorder traversal, or
     *        null if this node is the first
     */
    public DefaultMutableTreeNode getPreviousNode() {
    DefaultMutableTreeNode previousSibling;
    DefaultMutableTreeNode myParent = (DefaultMutableTreeNode)getParent();

    if (myParent == null) {
        return null;
    }

    previousSibling = getPreviousSibling();

    if (previousSibling != null) {
        if (previousSibling.getChildCount() == 0)
        return previousSibling;
        else
        return previousSibling.getLastLeaf();
    } else {
        return myParent;
    }
    }

    /**
     * Creates and returns an enumeration that traverses the subtree rooted at
     * this node in preorder.  The first node returned by the enumeration's
     * <code>nextElement()</code> method is this node.<P>
     *
     * Modifying the tree by inserting, removing, or moving a node invalidates
     * any enumerations created before the modification.
     *
     * @see    #postorderEnumeration
     * @return    an enumeration for traversing the tree in preorder
     */
    public Enumeration preorderEnumeration() {
    return new PreorderEnumeration(this);
    }

    /**
     * Creates and returns an enumeration that traverses the subtree rooted at
     * this node in postorder.  The first node returned by the enumeration's
     * <code>nextElement()</code> method is the leftmost leaf.  This is the
     * same as a depth-first traversal.<P>
     *
     * Modifying the tree by inserting, removing, or moving a node invalidates
     * any enumerations created before the modification.
     *
     * @see    #depthFirstEnumeration
     * @see    #preorderEnumeration
     * @return    an enumeration for traversing the tree in postorder
     */
    public Enumeration postorderEnumeration() {
    return new PostorderEnumeration(this);
    }

    /**
     * Creates and returns an enumeration that traverses the subtree rooted at
     * this node in breadth-first order.  The first node returned by the
     * enumeration's <code>nextElement()</code> method is this node.<P>
     *
     * Modifying the tree by inserting, removing, or moving a node invalidates
     * any enumerations created before the modification.
     *
     * @see    #depthFirstEnumeration
     * @return    an enumeration for traversing the tree in breadth-first order
     */
    public Enumeration breadthFirstEnumeration() {
    return new BreadthFirstEnumeration(this);
    }

    /**
     * Creates and returns an enumeration that traverses the subtree rooted at
     * this node in depth-first order.  The first node returned by the
     * enumeration's <code>nextElement()</code> method is the leftmost leaf.
     * This is the same as a postorder traversal.<P>
     *
     * Modifying the tree by inserting, removing, or moving a node invalidates
     * any enumerations created before the modification.
     *
     * @see    #breadthFirstEnumeration
     * @see    #postorderEnumeration
     * @return    an enumeration for traversing the tree in depth-first order
     */
    public Enumeration depthFirstEnumeration() {
    return postorderEnumeration();
    }

    /**
     * Creates and returns an enumeration that follows the path from
     * <code>ancestor</code> to this node.  The enumeration's
     * <code>nextElement()</code> method first returns <code>ancestor</code>,
     * then the child of <code>ancestor</code> that is an ancestor of this
     * node, and so on, and finally returns this node.  Creation of the
     * enumeration is O(m) where m is the number of nodes between this node
     * and <code>ancestor</code>, inclusive.  Each <code>nextElement()</code>
     * message is O(1).<P>
     *
     * Modifying the tree by inserting, removing, or moving a node invalidates
     * any enumerations created before the modification.
     *
     * @see        #isNodeAncestor
     * @see        #isNodeDescendant
     * @exception    IllegalArgumentException if <code>ancestor</code> is
     *                        not an ancestor of this node
     * @return    an enumeration for following the path from an ancestor of
     *        this node to this one
     */
    public Enumeration pathFromAncestorEnumeration(TreeNode ancestor){
    return new PathBetweenNodesEnumeration(ancestor, this);
    }


    //
    //  Child Queries
    //

    /**
     * Returns true if <code>aNode</code> is a child of this node.  If
     * <code>aNode</code> is null, this method returns false.
     *
     * @return    true if <code>aNode</code> is a child of this node; false if
     *          <code>aNode</code> is null
     */
    public boolean isNodeChild(TreeNode aNode) {
    boolean retval;

    if (aNode == null) {
        retval = false;
    } else {
        if (getChildCount() == 0) {
        retval = false;
        } else {
        retval = (aNode.getParent() == this);
        }
    }

    return retval;
    }


    /**
     * Returns this node's first child.  If this node has no children,
     * throws NoSuchElementException.
     *
     * @return    the first child of this node
     * @exception    NoSuchElementException    if this node has no children
     */
    public TreeNode getFirstChild() {
    if (getChildCount() == 0) {
        throw new NoSuchElementException("node has no children");
    }
    return getChildAt(0);
    }


    /**
     * Returns this node's last child.  If this node has no children,
     * throws NoSuchElementException.
     *
     * @return    the last child of this node
     * @exception    NoSuchElementException    if this node has no children
     */
    public TreeNode getLastChild() {
    if (getChildCount() == 0) {
        throw new NoSuchElementException("node has no children");
    }
    return getChildAt(getChildCount()-1);
    }


    /**
     * Returns the child in this node's child array that immediately
     * follows <code>aChild</code>, which must be a child of this node.  If
     * <code>aChild</code> is the last child, returns null.  This method
     * performs a linear search of this node's children for
     * <code>aChild</code> and is O(n) where n is the number of children; to
     * traverse the entire array of children, use an enumeration instead.
     *
     * @see        #children
     * @exception    IllegalArgumentException if <code>aChild</code> is
     *                    null or is not a child of this node
     * @return    the child of this node that immediately follows
     *        <code>aChild</code>
     */
    public TreeNode getChildAfter(TreeNode aChild) {
    if (aChild == null) {
        throw new IllegalArgumentException("argument is null");
    }

    int index = getIndex(aChild);        // linear search

    if (index == -1) {
        throw new IllegalArgumentException("node is not a child");
    }

    if (index < getChildCount() - 1) {
        return getChildAt(index + 1);
    } else {
        return null;
    }
    }


    /**
     * Returns the child in this node's child array that immediately
     * precedes <code>aChild</code>, which must be a child of this node.  If
     * <code>aChild</code> is the first child, returns null.  This method
     * performs a linear search of this node's children for <code>aChild</code>
     * and is O(n) where n is the number of children.
     *
     * @exception    IllegalArgumentException if <code>aChild</code> is null
     *                        or is not a child of this node
     * @return    the child of this node that immediately precedes
     *        <code>aChild</code>
     */
    public TreeNode getChildBefore(TreeNode aChild) {
    if (aChild == null) {
        throw new IllegalArgumentException("argument is null");
    }

    int index = getIndex(aChild);        // linear search

    if (index == -1) {
        throw new IllegalArgumentException("argument is not a child");
    }

    if (index > 0) {
        return getChildAt(index - 1);
    } else {
        return null;
    }
    }


    //
    //  Sibling Queries
    //


    /**
     * Returns true if <code>anotherNode</code> is a sibling of (has the
     * same parent as) this node.  A node is its own sibling.  If
     * <code>anotherNode</code> is null, returns false.
     *
     * @param    anotherNode    node to test as sibling of this node
     * @return    true if <code>anotherNode</code> is a sibling of this node
     */
    public boolean isNodeSibling(TreeNode anotherNode) {
    boolean retval;

    if (anotherNode == null) {
        retval = false;
    } else if (anotherNode == this) {
        retval = true;
    } else {
        TreeNode  myParent = getParent();
        retval = (myParent != null && myParent == anotherNode.getParent());

        if (retval && !((DefaultMutableTreeNode)getParent())
                   .isNodeChild(anotherNode)) {
        throw new InternalError("sibling has different parent");
        }
    }

    return retval;
    }


    /**
     * Returns the number of siblings of this node.  A node is its own sibling
     * (if it has no parent or no siblings, this method returns
     * <code>1</code>).
     *
     * @return    the number of siblings of this node
     */
    public int getSiblingCount() {
    TreeNode myParent = getParent();

    if (myParent == null) {
        return 1;
    } else {
        return myParent.getChildCount();
    }
    }


    /**
     * Returns the next sibling of this node in the parent's children array.
     * Returns null if this node has no parent or is the parent's last child.
     * This method performs a linear search that is O(n) where n is the number
     * of children; to traverse the entire array, use the parent's child
     * enumeration instead.
     *
     * @see    #children
     * @return    the sibling of this node that immediately follows this node
     */
    public DefaultMutableTreeNode getNextSibling() {
    DefaultMutableTreeNode retval;

    DefaultMutableTreeNode myParent = (DefaultMutableTreeNode)getParent();

    if (myParent == null) {
        retval = null;
    } else {
        retval = (DefaultMutableTreeNode)myParent.getChildAfter(this);    // linear search
    }

    if (retval != null && !isNodeSibling(retval)) {
        throw new InternalError("child of parent is not a sibling");
    }

    return retval;
    }


    /**
     * Returns the previous sibling of this node in the parent's children
     * array.  Returns null if this node has no parent or is the parent's
     * first child.  This method performs a linear search that is O(n) where n
     * is the number of children.
     *
     * @return    the sibling of this node that immediately precedes this node
     */
    public DefaultMutableTreeNode getPreviousSibling() {
    DefaultMutableTreeNode retval;

    DefaultMutableTreeNode myParent = (DefaultMutableTreeNode)getParent();

    if (myParent == null) {
        retval = null;
    } else {
        retval = (DefaultMutableTreeNode)myParent.getChildBefore(this);    // linear search
    }

    if (retval != null && !isNodeSibling(retval)) {
        throw new InternalError("child of parent is not a sibling");
    }

    return retval;
    }



    //
    //  Leaf Queries
    //

    /**
     * Returns true if this node has no children.  To distinguish between
     * nodes that have no children and nodes that <i>cannot</i> have
     * children (e.g. to distinguish files from empty directories), use this
     * method in conjunction with <code>getAllowsChildren</code>
     *
     * @see    #getAllowsChildren
     * @return    true if this node has no children
     */
    public boolean isLeaf() {
    return (getChildCount() == 0);
    }


    /**
     * Finds and returns the first leaf that is a descendant of this node --
     * either this node or its first child's first leaf.
     * Returns this node if it is a leaf.
     *
     * @see    #isLeaf
     * @see    #isNodeDescendant
     * @return    the first leaf in the subtree rooted at this node
     */
    public DefaultMutableTreeNode getFirstLeaf() {
    DefaultMutableTreeNode node = this;

    while (!node.isLeaf()) {
        node = (DefaultMutableTreeNode)node.getFirstChild();
    }

    return node;
    }


    /**
     * Finds and returns the last leaf that is a descendant of this node --
     * either this node or its last child's last leaf.
     * Returns this node if it is a leaf.
     *
     * @see    #isLeaf
     * @see    #isNodeDescendant
     * @return    the last leaf in the subtree rooted at this node
     */
    public DefaultMutableTreeNode getLastLeaf() {
    DefaultMutableTreeNode node = this;

    while (!node.isLeaf()) {
        node = (DefaultMutableTreeNode)node.getLastChild();
    }

    return node;
    }


    /**
     * Returns the leaf after this node or null if this node is the
     * last leaf in the tree.
     * <p>
     * In this implementation of the <code>MutableNode</code> interface,
     * this operation is very inefficient. In order to determine the
     * next node, this method first performs a linear search in the
     * parent's child-list in order to find the current node.
     * <p>
     * That implementation makes the operation suitable for short
     * traversals from a known position. But to traverse all of the
     * leaves in the tree, you should use <code>depthFirstEnumeration</code>
     * to enumerate the nodes in the tree and use <code>isLeaf</code>
     * on each node to determine which are leaves.
     *
     * @see    #depthFirstEnumeration
     * @see    #isLeaf
     * @return    returns the next leaf past this node
     */
    public DefaultMutableTreeNode getNextLeaf() {
    DefaultMutableTreeNode nextSibling;
    DefaultMutableTreeNode myParent = (DefaultMutableTreeNode)getParent();

    if (myParent == null)
        return null;

    nextSibling = getNextSibling();    // linear search

    if (nextSibling != null)
        return nextSibling.getFirstLeaf();

    return myParent.getNextLeaf();    // tail recursion
    }


    /**
     * Returns the leaf before this node or null if this node is the
     * first leaf in the tree.
     * <p>
     * In this implementation of the <code>MutableNode</code> interface,
     * this operation is very inefficient. In order to determine the
     * previous node, this method first performs a linear search in the
     * parent's child-list in order to find the current node.
     * <p>
     * That implementation makes the operation suitable for short
     * traversals from a known position. But to traverse all of the
     * leaves in the tree, you should use <code>depthFirstEnumeration</code>
     * to enumerate the nodes in the tree and use <code>isLeaf</code>
     * on each node to determine which are leaves.
     *
     * @see        #depthFirstEnumeration
     * @see        #isLeaf
     * @return    returns the leaf before this node
     */
    public DefaultMutableTreeNode getPreviousLeaf() {
    DefaultMutableTreeNode previousSibling;
    DefaultMutableTreeNode myParent = (DefaultMutableTreeNode)getParent();

    if (myParent == null)
        return null;

    previousSibling = getPreviousSibling();    // linear search

    if (previousSibling != null)
        return previousSibling.getLastLeaf();

    return myParent.getPreviousLeaf();        // tail recursion
    }


    /**
     * Returns the total number of leaves that are descendants of this node.
     * If this node is a leaf, returns <code>1</code>.  This method is O(n)
     * where n is the number of descendants of this node.
     *
     * @see    #isNodeAncestor
     * @return    the number of leaves beneath this node
     */
    public int getLeafCount() {
    int count = 0;

    TreeNode node;
    Enumeration enum = breadthFirstEnumeration(); // order matters not

    while (enum.hasMoreElements()) {
        node = (TreeNode)enum.nextElement();
        if (node.isLeaf()) {
        count++;
        }
    }

    if (count < 1) {
        throw new InternalError("tree has zero leaves");
    }

    return count;
    }


    //
    //  Overrides
    //

    /**
     * Returns the result of sending <code>toString()</code> to this node's
     * user object, or null if this node has no user object.
     *
     * @see    #getUserObject
     */
    public String toString() {
    if (userObject == null) {
        return null;
    } else {
        return userObject.toString();
    }
    }

    /**
     * Overridden to make clone public.  Returns a shallow copy of this node;
     * the new node has no parent or children and has a reference to the same
     * user object, if any.
     *
     * @return    a copy of this node
     */
    public Object clone() {
    DefaultMutableTreeNode newNode = null;

    try {
        newNode = (DefaultMutableTreeNode)super.clone();

        // shallow copy -- the new node has no parent or children
        newNode.children = null;
        newNode.parent = null;

    } catch (CloneNotSupportedException e) {
        // Won't happen because we implement Cloneable
        throw new InternalError(e.toString());
    }

    return newNode;
    }


    // Serialization support.
    private void writeObject(ObjectOutputStream s) throws IOException {
    Object[]             tValues;

    s.defaultWriteObject();
    // Save the userObject, if its Serializable.
    if(userObject != null && userObject instanceof Serializable) {
        tValues = new Object[2];
        tValues[0] = "userObject";
        tValues[1] = userObject;
    }
    else
        tValues = new Object[0];
    s.writeObject(tValues);
    }

    private void readObject(ObjectInputStream s)
    throws IOException, ClassNotFoundException {
    Object[]      tValues;

    s.defaultReadObject();

    tValues = (Object[])s.readObject();

    if(tValues.length > 0 && tValues[0].equals("userObject"))
        userObject = tValues[1];
    }

    final class PreorderEnumeration implements Enumeration {
    protected Stack    stack;

    public PreorderEnumeration(TreeNode rootNode) {
        super();
        Vector v = new Vector(1);
        v.addElement(rootNode);    // PENDING: don't really need a vector
        stack = new Stack();
        stack.push(v.elements());
    }

    public boolean hasMoreElements() {
        return (!stack.empty() &&
            ((Enumeration)stack.peek()).hasMoreElements());
    }

    public Object nextElement() {
        Enumeration    enumer = (Enumeration)stack.peek();
        TreeNode    node = (TreeNode)enumer.nextElement();
        Enumeration    children = node.children();

        if (!enumer.hasMoreElements()) {
        stack.pop();
        }
        if (children.hasMoreElements()) {
        stack.push(children);
        }
        return node;
    }

    }  // End of class PreorderEnumeration



    final class PostorderEnumeration implements Enumeration {
    protected TreeNode root;
    protected Enumeration children;
    protected Enumeration subtree;

    public PostorderEnumeration(TreeNode rootNode) {
        super();
        root = rootNode;
        children = root.children();
        subtree = EMPTY_ENUMERATION;
    }

    public boolean hasMoreElements() {
        return root != null;
    }

    public Object nextElement() {
        Object retval;

        if (subtree.hasMoreElements()) {
        retval = subtree.nextElement();
        } else if (children.hasMoreElements()) {
        subtree = new PostorderEnumeration(
                (TreeNode)children.nextElement());
        retval = subtree.nextElement();
        } else {
        retval = root;
        root = null;
        }

        return retval;
    }

    }  // End of class PostorderEnumeration



    final class BreadthFirstEnumeration implements Enumeration {
    protected Queue    queue;

    public BreadthFirstEnumeration(TreeNode rootNode) {
        super();
        Vector v = new Vector(1);
        v.addElement(rootNode);    // PENDING: don't really need a vector
        queue = new Queue();
        queue.enqueue(v.elements());
    }

    public boolean hasMoreElements() {
        return (!queue.isEmpty() &&
            ((Enumeration)queue.firstObject()).hasMoreElements());
    }

    public Object nextElement() {
        Enumeration    enumer = (Enumeration)queue.firstObject();
        TreeNode    node = (TreeNode)enumer.nextElement();
        Enumeration    children = node.children();

        if (!enumer.hasMoreElements()) {
        queue.dequeue();
        }
        if (children.hasMoreElements()) {
        queue.enqueue(children);
        }
        return node;
    }


    // A simple queue with a linked list data structure.
    final class Queue {
        QNode head;    // null if empty
        QNode tail;

        final class QNode {
        public Object    object;
        public QNode    next;    // null if end
        public QNode(Object object, QNode next) {
            this.object = object;
            this.next = next;
        }
        }

        public void enqueue(Object anObject) {
        if (head == null) {
            head = tail = new QNode(anObject, null);
        } else {
            tail.next = new QNode(anObject, null);
            tail = tail.next;
        }
        }

        public Object dequeue() {
        if (head == null) {
            throw new NoSuchElementException("No more elements");
        }

        Object retval = head.object;
        QNode oldHead = head;
        head = head.next;
        if (head == null) {
            tail = null;
        } else {
            oldHead.next = null;
        }
        return retval;
        }

        public Object firstObject() {
        if (head == null) {
            throw new NoSuchElementException("No more elements");
        }

        return head.object;
        }

        public boolean isEmpty() {
        return head == null;
        }

    } // End of class Queue

    }  // End of class BreadthFirstEnumeration



    final class PathBetweenNodesEnumeration implements Enumeration {
    protected Stack stack;

    public PathBetweenNodesEnumeration(TreeNode ancestor,
                       TreeNode descendant)
    {
        super();

        if (ancestor == null || descendant == null) {
        throw new IllegalArgumentException("argument is null");
        }

        TreeNode current;

        stack = new Stack();
        stack.push(descendant);

        current = descendant;
        while (current != ancestor) {
        current = current.getParent();
        if (current == null && descendant != ancestor) {
            throw new IllegalArgumentException("node " + ancestor +
                " is not an ancestor of " + descendant);
        }
        stack.push(current);
        }
    }

    public boolean hasMoreElements() {
        return stack.size() > 0;
    }

    public Object nextElement() {
        try {
        return stack.pop();
        } catch (EmptyStackException e) {
        throw new NoSuchElementException("No more elements");
        }
    }

    } // End of class PathBetweenNodesEnumeration



} // End of class DefaultMutableTreeNode